#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    vector<int> arrayRankTransform(vector<int> &arr)
    {
        vector<int> ans = arr;
        sort(arr.begin(), arr.end());
        unordered_map<int, int> arrMap;
        for (size_t i = 0, j = 0; i < arr.size(); i++)
        {
            if (arrMap[arr[i]] == 0)
            {
                arrMap[arr[i]] = j + 1;
                j++;
            }
        }

        for (size_t i = 0; i < ans.size(); i++)
        {
            ans[i] = arrMap[ans[i]];
        }
        return ans;
    }

    vector<int> arrayRankTransform_2(vector<int> &arr)
    {
        vector<int> sortedArr = arr;
        sort(sortedArr.begin(), sortedArr.end());
        unordered_map<int, int> ranks;
        vector<int> ans(arr.size());
        for (auto &a : sortedArr)
        {
            if (!ranks.count(a))
            {
                ranks[a] = ranks.size() + 1;
            }
        }
        for (int i = 0; i < arr.size(); i++)
        {
            ans[i] = ranks[arr[i]];
        }
        return ans;
    }
};
int main()
{
    Solution s;
    vector<int> arr = {37, 12, 28, 9, 100, 56, 80, 5, 12};
    vector<int> ans = s.arrayRankTransform(arr);
    for (auto &a : ans)
    {
        cout << a << " ";
    }
    cout << endl;
    return 0;
}